// 时间复杂度：O(nlogn)
// 空间复杂度：最坏O(n)，最优Ologn
// 不稳定排序

// 基本思想：通过一趟排序将无序序列分为独立的两个序列，第一个序列的值均比第二个序列的值小，
// 然后递归地排列两个子序列，以达到整个序列有序

// 步骤， 1. 从序列中找到一个基准， 2使用双指针，将序列中比基准大的元素移动到基准右侧，将比它小的移动到基准数左侧
// 最后遍历完，i之前的元素都小于基准数，i-1， 3. 将序列拆分为左右两个子序列，重复第二步，直到各个子序列只有一个元素，则排序结束
function quickSort(arr, left = 0, right = arr.length - 1) {
    if (arr.length > 1) {
        // lineIndex表示下一次划分左右子数组的索引位
        const lineIndex = partition(arr, left, right)
        // 如果左边子数组的长度不小于1，则递归快排这个子数组
        if (left < lineIndex - 1) {
            // 左子数组以 lineIndex-1 为右边界
            quickSort(arr, left, lineIndex - 1)
        }
        // 如果右边子数组的长度不小于1，则递归快排这个子数组
        if (lineIndex  < right) {
            // 右子数组以 lineIndex 为左边界
            quickSort(arr, lineIndex , right)
        }
    }
    return arr
}

function partition(arr, left, right) {
    // 基准值默认取中间位置的元素
    let pivotValue = arr[Math.floor(left + (right - left) / 2)]
    // 初始化左右指针
    let i = left
    let j = right
    // 当左右指针不越界时，循环执行以下逻辑
    while (i <= j) {
        // 左指针所指匀速小于基准值，则右移左指针
        while (arr[i] < pivotValue) {
            i++
        }
        // 右指针所指元素大于基准值，则左移右指针
        while (arr[j] > pivotValue) {
            j--
        }
        // 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序
        if (i <= j) {
            swap(arr, i, j)
            i++
            j--
        }
    }
    return i
}

// 快速排序中使用 swap 的地方比较多，我们提取成一个独立的函数
function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}

let arr = [6, 2, 1, 3, 7, 5, 4, 8]
console.log(quickSort(arr))

// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

function quickSort2(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        // 按照基准数的位置，将序列划分为左右两个子序列
        let index = partition2(arr, low, high)
        // 对左右两个子序列分别进行递归快速排序
        quickSort2(arr, low, index - 1)
        quickSort2(arr, index + 1, high)
    }
    return arr
}

function partition2(arr, low, high) {
    // 随机选择一个基准数
    let randIndex = Math.floor(Math.random() * (high - low)) + low;
    [arr[randIndex], arr[low]] = [arr[low], arr[randIndex]]
    let pivot = arr[low]
    let i = low + 1
    // 以最低位为基准数，然后将序列中比基准数大的元素移动到基准数右侧
    // 比基准数小的移动到基准数左侧，最后将基准数放到正确的位置上
    // 从基准数1位开始开始遍历，保证位置i之前的元素都小于基准数
    for (let j = i; j < arr.length; j++) {
        if (arr[j] < pivot) {
            // 将小于基准的元素arr[j] 与当前arr[i]进行交换，保证位置i之前的元素小于基准数
            [arr[i], arr[j]] = [arr[j], arr[i]]
            i++
        }
    }
    // 把基准放到正确的位置
    [arr[i - 1], arr[low]] = [arr[low], arr[i - 1]]
    // 返回基准的位置
    return i - 1
}
let arr2 = [6, 2, 1, 3, 7, 5, 4, 8]
console.log(quickSort2(arr2))